package formal.tree.recursion;

/**
 * 另一个树的子树
 *
 * @author DengYuan2
 * @create 2021-01-13 20:11
 */
public class E_572 {
    public static void main(String[] args) {
        // , null, null, null, null, 0, null
        Integer[] a = {3, 4, 5, 1, 2};
//        Integer[] a ={1,1,null};
        TreeNode t1 = TreeNode.generateTree(a);
        Integer[] b = {4, 1, 2};
//        Integer[] b = {1};
        TreeNode t2 = TreeNode.generateTree(b);
        boolean res = isSubtree(t1, t2);
        System.out.println(res);
    }


    /**
     * 官方-大神-一致
     * 大神的写法-思路：先搞定一个节点（递归），再分析左右节点（再递归）
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null ) {
            return false;
        }
        return subTreeHelper(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public static boolean subTreeHelper(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.val != t.val) {
            return false;
        }
        return subTreeHelper(s.left, t.left) && subTreeHelper(s.right, t.right);
    }


}
